#include <iostream>
#include <vector>
#include <stack>
#include <utility>

using namespace std;


struct Node {
    int x, y;
    int value;
    //key的0,1,2,3分别表示右下左上，value表示0或者1
    vector<pair<int, int>> path;
    Node(int x, int y, const vector<pair<int, int>>& path) : x(x), y(y), path(path) {}
};

bool dfs(vector<vector<int>>& maze, int startX, int startY, int endX, int endY) 
{
    int m = maze.size();
    int n = maze[0].size();

    // 用栈存储节点，栈中保存坐标和路径
    stack<Node> s;
    vector<vector<bool>> visited(m, vector<bool>(n, false));

    // 初始化栈
    s.push(Node(startX, startY, {{startX, startY}}));  // 初始路径为起点
    visited[startX][startY] = true;

    while (!s.empty()) 
    {
        Node node = s.top();
        s.pop();

        // 如果当前节点是终点，输出路径
        if (node.x == endX && node.y == endY) {
            cout << "Path found:" << endl;
            for (auto& p : node.path) {
                cout << "(" << p.first << ", " << p.second << ") ";
            }
            cout << endl;
            return true;
        }

        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            int newX = node.x + dir[i][0];
            int newY = node.y + dir[i][1];

            // 判断是否越界、是否是障碍物、是否已访问过
            if (newX >= 0 && newX < m && newY >= 0 && newY < n && maze[newX][newY] == 0 && !visited[newX][newY]) {
                // 标记为已访问
                visited[newX][newY] = true;

                // 新的路径
                vector<pair<int, int>> newPath = node.path;
                newPath.push_back({newX, newY});

                // 将新的节点和路径加入栈
                s.push(Node(newX, newY, newPath));
            }
        }
    }

    cout << "No path found." << endl;
    return false;
}

int main() {
    vector<vector<Node>> maze = {
        {Node(0,0), 1, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 1, 0, 0, 0},
        {0, 0, 0, 1, 1},
        {0, 0, 0, 0, 0}
    };

    int startX = 0, startY = 0;  // 起点
    int endX = 4, endY = 4;      // 终点

    dfs(maze, startX, startY, endX, endY);

    return 0;
}
